|
|
Scrabble
Picek, Radomír ; Glembek, Ondřej (referee) ; Smrž, Pavel (advisor)
This thesis describes the social table game Scrabble, and its realization in the form of computer games. Gradually examines all important aspects that affect the performance of the implementation. Especially after the election of the appropriate data structures retained for the vocabulary, affecting the efficiency of generating moves, and the selection of appropriate algorithms with regard to the maximum speed. There is particular emphasis on artificial intelligence opponent and its ability to compete not only amateurs, but professional SCRABBLE players.
|
|
|
Visualization of Longest Prefix Match Algorithms
Fomiczew, Jiří ; Matoušek, Jiří (referee) ; Kováčik, Michal (advisor)
This thesis describes the design and implementation of program for vizualization of algorithms for longest pre fix match (LPM), which is one of the most important tasks for packet classi cation and routing in TCP/IP networks. It describes necessary theory and details about selected algorithms - Trie, Tree Bitmap and CPE. Furthermore, it describes the design and implementation of program for vizualization of the search process of these algorithms with emphasis on the potential use for educational purposes. Finally, it describes the possibilities for future development and expansion of the program.
|
|
|
Graphical Demonstration of Selected Route Lookup Algorithm
Ohrádka, Marek ; Kaštil, Jan (referee) ; Puš, Viktor (advisor)
This bachelor's thesis deals with IP routing and different routing protocols. It describes different solutions of the longest prefix matching, advantages and disadvantages of different approaches. Shows the concept of the trie data structure and its alternatives. Describes the Shape Shifting Trie data structure in detail, as well as process of its creation and the way of traversing the nodes in SST route lookup algorithm. At last, application design and implementation is described. Main purpose of the application is to graphically demonstrate the function of SST route lookup algorithm. This thesis shows decomposition approach to this task, describes major problems and its solution.
|
|
|
Mapping of Match Tables from P4 Language to FPGA Technology
Kekely, Michal ; Matoušek, Jiří (referee) ; Kořenek, Jan (advisor)
This thesis deals with design and implementation of mapping of match action tables from P4 language to FPGA technology. Goal of the thesis was to describe key principles, which need to be understood in order to design such a mapping and function of algorithms needed, apply these principles by implementing them and analyze the speed and memory requirements of such an implementation. Outcome provides configurable hardware unit capable of classifying packets and connection between the unit and match action tables from P4 language. The implementation is based on DCFL algorithm and requires less memory compared to HiCuts and HyperCuts algorithms while being comparably fast at worst-case scenarios.
|
|
|
Longest Prefix Match Algorithms
Sedlář, František ; Puš, Viktor (referee) ; Tobola, Jiří (advisor)
This bachelor's thesis deals with a description of basic longest prefix match (LPM) algorithms. Another algorithm - LC Trie - was added to existing implementations into the Netbench library. All the algorithms which the library includes were tested with real groups of IPv6 prefixes. They were compared on the basis of previously obtained data. Testing scripts for each of the algorithms were implemented as well as scripts for downloading groups of prefixes from significant sources on the internet.
|
|
|
Longest Prefix Match Algorithms
Sedlář, František ; Matoušek, Jiří (referee) ; Tobola, Jiří (advisor)
This master's thesis explains basics of the longest prefix match (LPM) problem. It analyzes and describes chosen LPM algorithms considering their speed, memory requirements and an ability to implement them in hardware. On the basis of former findings it proposes a new algorithm Generic Hash Tree Bitmap. It is much faster than many other approaches, while its memory requirements are even lower. An implementation of the proposed algorithm has become a part of the Netbench library.
|
|
|
Slovak Pattern-based Morphology
Klocok, Andrej ; Dytrych, Jaroslav (referee) ; Smrž, Pavel (advisor)
Theaimofthisthesisistogetacquaintedwithmethodsofmorphologicalanalysis,representation of data of morphological dictionaries, creation of system based on technical patterns for flective morphology of Slovak language. From this system is derived a morphological analyzer, which lemmatizes input words, determines their pattern and a morphological tag, a tool for comparison and evaluation of stemmers, which evaluates stemmers based on a derivative dictionary, a tool for reconstruction of diacritics, which was created as an auxiliary tool. In the last chapters of thesis, individual tools are assessed, morphological analyzer is compared with available alternative,two implementations of Slovak stemmers are evaluated by the tool for stemmer evaluation and the further development of tools is indicated.
|
|
|
Compression Methods Based on Context Modelling
Gach, Tomáš ; Drábek, Vladimír (referee) ; Bařina, David (advisor)
The aim of this thesis is to describe basic properties of the context-based compression methods. Modelling procedure is presented together with the principle of an arithmetic coding. Gradually the PPM, CTW, and PAQ methods are introduced together with the possible implementation of the basic PPM probability model. The performance of context-based, dictionary and the most currently used methods of data compression is being compared. Based on obtained results, the possible usage of PPM methods is summarized.
|
|
|
Scrabble for Mobil Phones
Kaněčka, Ondřej ; Kunc, Michael (referee) ; Schönecker, Rudolf (advisor)
This paper deals with an usage of searching algorithms and lexical data structures for platforms with limited computing power and accessible memory (celluar phones and similar) in SCRABBLE brand crossword game. There are also shown its advantages and disadvantages on this platform. The Appel-Jacobson searching algorithm is used to search possible moves. The lexicon with all words is available for this algorithm. It's stored in Directed Acyclic Word Graph (DAWG), which provides fast data searching and data compression too, so the size of the lexicon is comparatively small considering the target platform. The final Java application for celluar phones (MIDP 2.0) adds graphical interface and game control so it provides playing SCRABBLE brand crossword game against artificial intelligence or against human.
|
|
|
Morphological Analyser Implemented as FSAs
Černý, Stanislav ; Černocký, Jan (referee) ; Smrž, Pavel (advisor)
We describe morphemic analyser using dictionary approach. Dictionary is saved as deterministic finite state automata. Another part of text deals with analysis of numerals, especially retrieving numeric value from that words. Besides the analysis there is description of generating word-formation relationships in this work.
|
guest ::
